package com.tsx.leetcode.hot100.easy;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/majority-element">多数元素</a>
 * 1. 利用哈希表的特性，key为数组每个元素值，value为出现的次数
 * 2. 若哈希表没有存在元素，就设置为1，存在的话就+1
 * 3. 判断将最大次数值去做比较依次更新
 */
public class Q169MajorityElement {
    public static void main(String[] args) {
        int[] nums = new int[]{2, 2, 2, 1, 3, 4, 2};
        int res = majorityElement(nums);
        System.out.println("res = " + res);
    }

    /**
     * 使用哈希表计数法
     *
     * @param nums 数组
     * @return 众数
     */
    public static int majorityElement(int[] nums) {
        int maxCount = 0; // 出现最大次数
        int result = 0; // 众数
        Map<Integer, Integer> countMap = new HashMap<>(); // 存储对应数字的次数

        for (int num : nums) {
            int count = countMap.getOrDefault(num, 0) + 1; // 当map不存在的时候就是出现1次 存在的话就多1次
            countMap.put(num, count); // 把map更新

            if (count > maxCount) { // 若次数大于记录的最大次数值
                maxCount = count; // 更新最大次数
                result = num; // 更新结果
            }
        }
        return result;
    }

    /**
     * votes 记录当前候选人的票数，x 为当前候选人。
     * 遍历数组，若票数为0则更换候选人为当前数，并重置票数。
     * 若当前数等于候选人，票数加1，否则减1。
     * 最终x即为多数元素。
     *
     * @param nums 数组
     * @return 众数
     */
    public static int majorityElementByMoore(int[] nums) {
        int votes = 0;
        int x = 0;
        for (int num : nums) {
            if (votes == 0) {
                x = num;
            }
            if (num == x) {
                votes += 1;
            } else {
                votes -= 1;
            }
        }
        return x;
    }
}
